package listbyorder.access001_100.test33;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/5/30 11:02
 */
public class Solution1 {

    // 方法一： 自己的解法
    // 首先遍历一遍数组，找出分割位置
    // 然后判断target可能存在的位置
    // 然后进行二分查找即可
    public int search(int[] nums, int target) {
        if(nums == null || nums.length == 0) return -1;
        // 首先进行一轮遍历，找出分割点
        int i = 1;
        int len = nums.length;
        for (; i < len; i++) {
            if (nums[i] < nums[i - 1]) {
                break;
            }
        }
        if (i == len) {
            return getAns(nums, 0, len - 1, target);
        }
        if (nums[0] <= target) {
            return getAns(nums, 0, i - 1, target);
        } else {
            return getAns(nums, i, len - 1, target);
        }
    }

    private int getAns(int[] nums, int left, int right, int target) {
        if (left > right) return -1;
        int mid = 0;
        while (left <= right) {
            mid = (left + right) >> 1;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                left++;
            } else {
                right--;
            }
        }
        return -1;
    }
}
